package 二叉树;

import java.util.HashMap;
import java.util.Map;

public class buildTree {
    Map<Integer,Integer> map=new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n=preorder.length;
        for(int i=0;i<inorder.length;++i){
            map.put(inorder[i],i);
        }
        return dfs(preorder,inorder,0,n-1,0,n-1);
    }


    public TreeNode dfs(int[] preorder,int[] inorder,
                    int preorderLeft,int preorderRight,
                        int inorderLeft,int inorderRight){
        if(preorderLeft>preorderRight){
            return null;
        }
//        先序遍历第一个节点就是根节点
        int preorderRoot=preorderLeft;
        TreeNode root=new TreeNode(preorder[preorderRoot]);
        int inorderRoot=map.get(preorder[preorderLeft]);

        int size_left_subtree = inorderRoot - inorderLeft;

        root.left=dfs(preorder,inorder,preorderLeft+1,preorderLeft+size_left_subtree,inorderLeft,inorderRoot-1);
        root.right=dfs(preorder,inorder,preorderLeft+size_left_subtree+1,preorderRight,inorderRoot+1,inorderRight);
        return root;

    }
}
